백준 9935번

오늘 풀어본 문제는 백준의 9935번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 4

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 “FRULA”를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 $1$ 보다 크거나 같고, $1,000,000$ 보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 $1$ 보다 크거나 같고, $36$ 보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 $0, 1, \cdots, 9$ 로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

풀이과정

1번째 시도

문제를 보고 스택을 이용하여 문제를 해결해야 할 것 같다는 생각이 들었다. 주어진 테스트 케이스에서 연쇄적으로 ‘폭발’이 일어나는 모습을 확인할 수 있었기 때문이다.

예를 들어 “C4” 라는 문자열이 폭발하는 문자열이고, “AAAACC44AAAA” 라는 문자열이 있다고 하면 첫 번째 폭발에서 문자열이 “AAAAC4AAAA” 가 되고 다시 한 번 폭발이 더 일어나 “AAAAAAAA” 가 된다. 이와 같이 폭발 이후에 새로운 ‘폭탄 문자열’ 이 생길 수 있기 때문에 각 문자열의 문자들을 차례로 순회하는 방식으로 문제를 해결할 수 있을 것이라고 생각하였다.

코드는 다음과 같이 작성하였다. 문자열을 출력하기 위해서 문자들을 저장하기 위한 스택은 std::stack 대신 std::deque 를 사용하였다.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int length;
	string input, bomb;
	ostringstream result;

	cin >> input;
	cin >> bomb;

	length = bomb.length();

	int streak = 0;
	deque<char> dq;
	stack<int> prevStreaks;

	for (int i = 0; i < input.length(); i++) {
		if (input[i] == bomb[streak]) {
			dq.push_back(input[i]);
			streak++;

			if (streak == length) {
				for (int i = 0; i < length; i++) {
					dq.pop_back();
				}

				if (prevStreaks.empty()) {
					streak = 0;
				}
				else {
					streak = prevStreaks.top();
					prevStreaks.pop();
				}
			}
		}
		else if (input[i] == bomb[0]) {
			dq.push_back(input[i]);

			prevStreaks.push(streak);
			streak = 1;
		}
		else {
			streak = 0;
			
			while (!prevStreaks.empty()) {
				prevStreaks.pop();
			}

			while (!dq.empty()) {
				result << dq.front();
				dq.pop_front();
			}

			result << input[i];
		}
	}

	while (!dq.empty()) {
		result << dq.front();
		dq.pop_front();
	}

	string resultString = result.str();
	if (resultString == "") {
		cout << "FRULA";
	}

	cout << resultString;

	return 0;
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

간만에 스택을 사용하는 문제가 나왔던 것 같다. 보통 그래프 탐색 문제를 BFS나 다른 알고리즘을 이용하여 풀다보니 잘 안쓰게 되는 것 같다.

그러고 보니 세미나에서 배웠던 내용중에 BFS와 DFS를 모두 이용해야 하는 내용이 있었던 것 같은데, 그게 뭔지 기억이 잘 안난다… 조만간 복습을 한 번 해야할 것 같다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/9935

← Previous Post Next Post →